Peer-to-Peer file-sharing technologies are being rapidly adopted to distribute digital information (e.g., multimedia such as movies, TV, music; software; and imagery). One reason for the growth of P2P usage relates to the economics of content distribution. In most cases, the content publisher benefits by lower cost distribution of data. The content consumers benefit by obtaining content faster. This is especially valid for flash crowds that occur with popular data that would otherwise overload the capacity of a publisher's web servers.
While a client-server topology may suffice for limited download access, popular web sites have traditionally resorted to using Content Distribution Network (CDN) services to provide sufficient bandwidth to handle larger crowds. There are now various commercial CDN services available (e.g., Akamai, L3, Limelight). However, with such CDN services, bandwidth and data delivery costs scale linearly with the number of users interested in downloading the site's digital information. As large downloads (e.g., TV shows and movies) become more popular, the distribution costs associated with CDN services are high. P2P technologies offer a way to dramatically reduce such distribution costs.
From a general perspective, a P2P network takes advantage of the numerous, diverse connectivity between participants in a network and the cumulative upload/download bandwidth of all network participants. A pure peer-to-peer network does not have the notion of clients or servers, but only equal peers that each simultaneously function as both “client” and “server” to the other peers in the network. This is very different from the conventional client-server approach wherein one or more servers would be coupled with a number of clients. Peer-to-peer networks are typically used for connecting peers via largely ad hoc connections and are commonly used for sharing content. Unlike the client-server approach, as the number of peers grows, the aggregate network bandwidth of the set of peers grows. Thus, each peer has the potential to obtain the composite of the content faster, there is less chance for denial of service on the part of the content source, and the content source provider's computation and network utilization remains relatively low.
In practice, there are three distinct classes of P2P based distribution technologies: live streaming, download, and hybrid. P2P live streaming technologies (e.g., PPLive) deliver live audio and/or video and must satisfy applicable quality-of-service requirements. For example, the data must arrive in linear order to support playback of content (note that buffering allows some slop in arrival order) while maintaining sufficient bit rate in order to sustain playback. Furthermore, because the content is live, peers do not typically store significant amounts of content other than what is buffered locally. With asymmetric broadband technologies that offer faster download rates compared to upload rates, the ability to leverage peers in distributing video is diminished when the effective upload bandwidth on the peer's Internet connection is less than or comparable to the video content's encoding bit-rate. Hence, higher bit rate content requires additional content servers to supplement the bandwidth provided by the peers, which in turn drives up distribution costs. Because of bit-rate limitations, live streaming technologies are typically used with lower bit-rate media such as live audio and low bit-rate video streams.
With P2P download technologies, such as the original BitTorrent protocol, the digital information is delivered on a “best effort” basis with data being delivered to each peer in no particular order. Hence, traditional P2P download technologies are typically not suitable for video streaming applications, but offer lower distribution costs. Many companies are now offering P2P download-based services with BitTorrent-based protocols being among the most commonly used mechanisms.
Hybrid P2P technologies (also referred to as “peer assisted”) enable streaming while simultaneously allowing content to be stored locally on peers. Thus compared to P2P live streaming, a larger pool of peers is available to supply video content to fellow peers. Because video is stored locally, premium content usually must have some form of content protection mechanism (e.g., encrypted file systems, DRM technologies, etc.). There are now many companies offering such hybrid P2P technologies, including VeriSign, Inc., Akamai Technologies, Pando, iTiva, and BitTorrent, Inc. Hybrid P2P technologies typically offer improved quality of service. Most of these efforts have focused on combining P2P-based networks with Content Delivery Network (CDN) services that supplement the P2P network bandwidth in order to ensure higher quality-of-service to individual peers. Some of these (e.g., iTiva) also leverage web proxy servers provided by ISPs to supplement the CDN and P2P networks. The objectives of these hybrid technologies are typically to enhance the quality-of-service for peers, such as enabling streaming video delivery, while reducing distribution costs for content providers and ISPs. However, the use of web and CDN services to supplement P2P bandwidth adds distribution costs over pure P2P-based services. Hence the use of CDN services should typically be minimized without sacrificing end user quality of service.
While content providers and the content consumers enjoy the benefits of P2P, the consumers' Internet service providers (ISPs) do not appreciate the massive data exchange across the peering overlay network and the grossly inefficient use of network resources and bandwidth. Specifically, popular P2P technologies (e.g., BitTorrent) tend to ignore peer locality considerations when matching peers with each other. Hence, peer-to-peer communications are likely to leave the local ISP's network through key network resources that connect to other ISPs. Many commercial peer-to-peer technologies are now integrating various heuristics to group peers that are “nearby”, such as within the ISP's local network. Hence, use of “peer locality” to match peers helps make P2P technologies more appealing to ISPs by reducing network congestion with added benefit of enhancing P2P performance for peers.
Peer-to-peer (P2P) technologies provide significantly lower cost mechanisms for content providers seeking to distribute digital information to many different interested parties. However, the analysis of P2P performance and scaling characteristics show that existing peer selection methods can lead to sub-optimal content distribution performance.
BitTorrent Terminology
Some general terminology descriptions may be helpful and are included herein for convenience:                BitTorrent client—a computer program that implements a peer that uses the BitTorrent protocol. The client software may be installed on a variety of devices, such as personal computers, set top boxes, and portable device such as cell phones or media players.        BitTorrent protocol—a P2P protocol used for distributing content via a swarm.        Content Distribution Network or Content Delivery Network (CDN)—a system of Internet-interconnected computers that cooperate transparently to deliver content directly to interested end users.        current peer—the peer currently under consideration.        distributed hash table (DHT)—a decentralized, network-based system that provides a lookup service similar to a hash table.        flash crowd—a sudden network traffic surge caused by a significant influx of users attempting to access the same content.        Mainline—an open source BitTorrent client developed by BitTorrent, Inc. that serves as the reference implementation of the BitTorrent protocol.        miscreant peer—any peer that by design (as opposed to circumstances) does not comply with the implied sharing nature of the swarm.        non-seed—any peer that does not have all the content.        non-origin peer—any peer that is not an origin peer.        non-origin seed—any seed that is not an origin seed.        origin peer—any peer that is controlled by the content publisher and/or CDN and whose primary function is facilitating the distribution of content.        origin seed—any seed that is controlled by the content publisher and/or CDN and can be brought on-line or removed based on demand, and is typically used to initiate distribution of content.        origin server—the original content source computer network service from which the content distribution infrastructure obtains content to disseminate, typically operated by CDN services or content publisher.        overlay network—a logical network that is built on top of another (physical or lower-level logical) network, wherein this typically refers to the communication topology among peers.        peer—any piece-sharing participant in a swarm.        peer-list—a list of peer identifiers, usually Internet protocol addresses and ports.        peer selection algorithm—method used to select a subset of peers in the swarm.        piece—a portion of the content being shared by a swarm.        proxy server—a computer network service that allows clients to make indirect network connections to other network services used to control references locally (ISP, business, etc.). Proxy servers typically cache content locally and are thus leveraged to alleviate traffic on key network resources.        remote peer—a peer on the peer-list of the current peer.        seed—any peer that has all the content.        server—a computer network service.        swarm—a group of P2P processes that interact with each other via a particular file distribution protocol for the purpose of sharing specific content The group is largely composed of peers, but also includes “servers” such as the tracker, web server(s), and proxy server(s).        torrent—the content (unique file or set of files) to be distributed within a swarm—plus a torrent file.        torrent file—a small file containing meta information about a torrent. The file contains unique identifiers (block hashes) for the content and its pieces, as well as the URL(s) for the associated tracker(s).        tracker—a network-based service that helps peers in a swarm find each other, wherein the tracker functionality can be centralized or distributed.        distributed swarm—a swarm that does not require the use of a centralized tracker (trackerless) and the tracker functionality is implemented by peers.BitTorrent Overview        
BitTorrent has been one of the most popular protocols for file-sharing and will be used herein for illustrative purposes as an example of the P2P system. It should be noted that the BitTorrent descriptions are based on the present state of the published materials of the BitTorrent protocol and subject to change.
BitTorrent is a protocol that allows a content provider to distribute content to a swarm of peers. The peers within the swarm will then disseminate parts of the content to each other in a peer exchange fashion such that as one peer is obtaining new pieces of content, it is simultaneously sharing its other pieces of content with other peers. One of the features that makes BitTorrent unique is that it provides a built-in mechanism to help facilitate the fair distribution of content and to help prevent selfishness on the part of peers by using a game theoretical “tit-for-tat” piece distribution algorithm. However, there are ways to manipulate this equal distribution scheme and variants (e.g., miscreant peers) have evolved that create priority ranking as well as disrupting equitable sharing which is sometimes referred to as “free riding.”
The functionality of a BitTorrent system is well publicized and known to those skilled in the art. However for completeness, a simplified high-level process flowchart for a BitTorrent system is shown in FIG. 1. Initially, there is some content file from a content provider that is prepared for sharing 105. For example, the content provider can be a large corporation or enterprise that uploads the data file to a company server for preparation (e.g., transcoding, DRM, watermarking, etc.), or it could be an independent music artist that prepares a new music video for dissemination to its fans.
The content file is packaged in a format that adheres to the respective P2P protocol being used for the dissemination 110. For example, a large content file will typically be distributed as pieces. Packaging in BitTorrent typically entails generating cryptographic hash values for each of these pieces to ensure their integrity, as well as generating a cryptographic hash of the entire content set. For example, one hash version is the US Secure Hash Algorithm 1 (SHA-1). These hashes are placed in a metafile (i.e., the .torrent file in BitTorrent) describing the information about the content to be distributed via P2P. The content data itself can be any form of digitized data and may consist of one or more files, folders, etc. In one example, the content file is a video and is packaged according to the BitTorrent protocol.
Once the content file has been packaged according to the appropriate P2P requirements, the content is registered with some form of tracker and a copy is placed on some origin seed 115. The metafile with the information about the content is published 120, such as by placing the .torrent file on a website or a syndication feed (e.g., an RSS feed). After the P2P file has been published 120, the content file is then available for downloading.
Peers will join the swarm 125 by downloading the metafile and registering with the tracker to initiate the transfer process. Upon request, the tracker will supply a peer with a list of other peers 130. The tracker will use its peer selection algorithm to determine which peers should go on any given peer-list. When a peer receives a peer-list from the tracker, it attempts to connect to the peers specified on that list 135. Peers then exchange pieces of content with their connected peers 140. At some point (typically determined by the end user), the peer will leave the swarm 145. If the peer leaves the swarm after having obtained all the content (typical), it is said to have been successful.
Referring to FIG. 2, a block diagrammatic presentation of a BitTorrent P2P system 210 is depicted for delivering content 220. The intent of the system is for all the peers in the overlay network of peers 270 to each ultimately obtain a full copy of the content. For convenience, only a few elements are shown, however there can be anywhere from one to hundreds of thousands of participants in a P2P swarm. The BitTorrent protocol in this example uses several components, namely torrent files 230, web servers 240, tracker servers 250, origin seed peers 290, and non-origin peers 280. It should be understood that the P2P technology is highly dynamic and that the details herein are intended to provide an understanding of the BitTorrent system at some particular time and may not reflect the most recent protocol version, and some of the command instructions and particulars may differ.
The original content owner/distributor with some content 220 to be distributed will use a complete copy of the content file(s) to generate a torrent file 230. A torrent file 230 is typically composed of a header plus a number of cryptographic hashes for the pieces of the original content file(s), where each piece of the file is a portion (e.g.: 256 KB) of the whole file. The header information typically denotes the IP address or URL of the tracker 250 for the torrent file 230, as the BitTorrent client must be registered with the tracker 250. Once created, the torrent file 230 is then published on a publicly accessible web server 240 or made available in other forms such as a Really Simple Syndication (RSS) feed.
An origin server or web server 240 is typically the initial distribution content point wherein the content provider will post the availability of some content such as a movie trailer onto a web server 240 for dissemination to the public or to some restricted users. The content itself is not on the web server, only the information about the content. Content providers may own their own servers, or they can use third party web servers. While a web server 240 is used in this example, there are many embodiments that operate with other distribution mechanisms such as via an RSS feed.
The torrent's unique id (the cryptographic has defined in the torrent file 230) is registered with the tracker 250, and the origin seed peer(s) 290 are established with a full copy of all the content pieces comprising the content 220 and the torrent file 230. The origin seed peer(s) 290 start with all the content and will seed the other non-seed peers in the overlay network of peers 270. A new peer needs to register itself with the tracker 250 in order to join the network of peers 270. It does this by contacting the Web Server 240 to obtain the torrent file 230 that specifies the address of the tracker 250. The new peer then contacts the tracker 250 to request the addresses of other peers within the overlay network of peers 270. The tracker 250 then uses peer selection software 260 to randomly choose a subset of peers that it knows about; creates a list of addresses of these selected peers; and sends the resultant list of peer addresses (which will subsequently be referred to as a peer-list) to the requester. Because of the size limit (typically 50 peers) of the peer-list provided by the tracker and mainline BitTorrent's random peer selection, the probability of creating an isolated clique in the overlay network of peers 270 is relatively low, which typically ensures robust network routes for piece distribution.
There are two ways that a current peer can establish a connection with another peer. The first way is when the current peer contacts a remote peer as a result of receiving the remote peer's address from the tracker. The second way is when another peer contacts the current peer. There is an upper limit on the number of remote connections that a current peer can establish. The upper limit is a configuration parameter that according to the BitTorrent reference implementation defaults to eighty. At any point during the piece exchange process, peers may join or leave the swarm's peering network 270. Because of the highly volatile nature of these swarms, a peer will re-request an updated list of peers from the tracker 240 periodically (typically between five and thirty minutes—based on default parameters from the BitTorrent reference implementation). This ensures the robustness of the swarm assuming the tracker 240 remains operational.
The tracker 250 is a network-based server and centrally coordinates the P2P transfer of files among the users. BitTorrent trackers are software server toolkit applications, and XBT, BNBT and CBTT are open source examples of BitTorrent tracker toolkits. Any non-origin peer 280 connects to the tracker 250 and requests a peer-list. The tracker 250 responds by providing the peer 280 with a peer-list that it can use to obtain pieces of the content file from the other peers in the overlay network of peers 270. Typical trackers, such as XBT, create the peer-list by randomly selecting peers that the tracker believes are currently in the swarm—but excluding the requesting peer. If the tracker 250 fails or is taken offline, peers 280 will be unable to connect to additional peers and thereby may be unable to continue sharing those P2P files.
The tracker 250 maintains information about the BitTorrent peers that it has registered. In particular, the tracker identifies each peer that is participating in the network of peers 270. It also typically tracks information that it receives each time it is contacted by a peer such as the number of bytes of content that it has uploaded, the number of bytes of content that it has downloaded, and the number of bytes of content that it still lacks.
The origin seeds 290 and other peers 280 typically transfer pieces (e.g., 256 KB portions) of the content file among themselves using a complex, non-cooperative, tit-for-tat algorithm. After a piece is downloaded, the current peer will validate that piece against the cryptographic hash for that piece. As noted, the hash for that piece is contained in the torrent file 230. When a piece is validated, the current peer is subsequently able to share it with other peers in its peer set (which is a subset of the entire network of peers 270) who have not yet obtained it. The determination of which piece to request from another peer is done using a rarest piece first policy which is used exclusively after the first few randomly selected pieces have been obtained by a peer (typically three pieces but this is a configuration parameter). Because each peer announces to all peers in its peer-set each new piece it has obtained (via a HAVE message), all peers 280 are able to keep copy counts on each piece and determine within their peer-set which piece or pieces are rarest (i.e., lowest copy count). When a non-seed peer has obtained all pieces for the file, it can then switch to being a seed for the content 220.
A present version of the BitTorrent system uses a distributed hash table (DHT) based tracker mechanism. This approach increases swarm robustness even with tracker failures or otherwise without a tracker.
Message Protocol The BitTorrent protocol and behavior are well publicized and known to those skilled in the art. Certain elements and behaviors associated with the BitTorrent protocol are highlighted herein for convenience. When describing specific parameters associated with the BitTorrent protocol, default values associated with the mainline BitTorrent implementation are used. Note that these values may be modified in different BitTorrent implementations.
The mainline BitTorrent message protocol includes 11 primary messages (excluding any custom or “Fast Extensions”). All intra-peer messages are typically sent using TCP whereas peer-tracker messages are typically sent using HTTP, TCP or sometimes UDP. While the commands may vary depending upon the version of the BitTorrent software being utilized, several basic functions are explained herein for exemplary purposes.
Upon entering a swarm, each peer is in the choked and not interested states. Once a peer has obtained its initial peer-set (up to fifty peers by default) from the tracker, it will initiate a HANDSHAKE message to forty peers by default. The upper bound on the number of peer connections is eighty. Thus, each peer keeps a number of connection slots available for peers who are not in its immediate peer-set. This reduces the probability that a clique will be created. The connections are maintained by periodically sending KEEP ALIVE messages.
Once two-way handshaking between peers is complete, each peer will send the other a BITFIELD message that contains an encoding of the pieces that that peer has. If a peer has no pieces, no BITFIELD message is sent. Upon receiving a BITFIELD message, a peer will determine if the remote peer has pieces it needs. If so, it will schedule an INTERESTED message. The remote peer will process the INTERESTED message by invoking its choker algorithm. The output from the remote peer's choker (upload side) is an UNCHOKE or CHOKE message. The response to an INTERESTED message is typically nothing or an UNCHOKE message. Once the peer receives an UNCHOKE message, the piece picker algorithm is invoked on the download side of the peer and a REQUEST message will be generated for a chunk, that is, a 16 KB (16,000 bytes) chunk within a piece. The remote peer will respond with a PIECE message that contains the 16 KB chunk of data. This response will in turn result in additional REQUESTS being sent.
When all 16 KB chunks within a piece have been obtained, the current peer will send a HAVE message to all peers to which it is connected. Upon receipt of the HAVE message, a remote peer may decide to schedule an INTERESTED message for that peer which results in an UNCHOKE message and then REQUEST and PIECE messages being exchanged. Thus, the protocol ensures continued downloading of data among all connected peers. Now, should a current peer have completely downloaded all content available from a particular remote peer, it will send a NOT INTERESTED message to that remote peer. Upon receipt of the NOT INTERESTED message, the remote peer will schedule a CHOKE message if the peer was currently in the unchoke state. Likewise, the remote peer will periodically “choke” and “unchoke” interested peers via the choker algorithm. Last, when a peer has made a request for all pieces of content, it will enter “endgame” mode. Here, requests to multiple connected peers for the same piece can occur. Thus, a peer will send a CANCEL message for that piece to those other peers when one remote peer has responded with the requested 16 KB chunk.
Choker Algorithm
There are two distinct choker algorithms, each with very different goals. The first is the choker algorithm used by a seed peer. Here, the goal is not to select the peer whose upload data transfer rate is best but instead maximize the distribution of pieces. In the case of non-seed peer, it uses a sorted list of interested, connected peers based on upload rates as one of the key determining factors. That is, it wants to try to find the set of peers with whom it can best exchange data.
The seed choker algorithm (SCA) generally only considers peers that have expressed interest in the current peer. First, the SCA orders all of its unchoked peers according to the time they were last unchoked with most recently unchoked peers listed first within a twenty second window. All other connected peers outside that window are ordered by their upload rate. In both cases, the fastest upload rate is used to break ties between peers. Now, during two of the three rounds, the algorithm leaves the first three peers unchoked and unchokes another randomly selected peer. This is known as the optimistic unchoked peer. During the third round, the first four peers are left unchoked and the remaining peers are sent CHOKE messages if they are currently in the unchoked state.
Both choker algorithms are scheduled to run every ten seconds and can be invoked in response to INTERESTED/NOT INTERESTED messages. Each invocation of the choker algorithm counts as a round. There are three distinct rounds that both choker algorithms cycle through.
For the non-seed choker algorithm, at the start of round one, (i.e., every thirty seconds, by default), the algorithm chooses one peer at random that is choked and interested. As in SCA, this is the optimistic unchoked peer (OUP). Next, the non-seed choker algorithm orders all peers that are interested and have sent at least one data block to the current peer in the last thirty second time interval, otherwise that remote peer is consider to be “snubbed”. Snubbed peers are excluded from being unchoked to prevent free riders and ensure that peers share data in a relatively fair manner. From that ordered list, the three fastest peers are unchoked. If the OUP is one of the three fastest, a new OUP is determined. The OUP is only unchoked on every third round.
Piece Picker
The piece picker is a two-phase algorithm. The first phase is “random”. When a non-seed peer has no content, it selects three pieces at random to download from peers that “have” those particular pieces. Once a peer has those three pieces, it shifts to a second phase of the algorithm which is based on a “rarest piece first” policy. Here, each piece's count is incremented based on HAVE and BITFIELD messages. For each remote peer that has unchoked the current peer, the piece with the lowest count (but not zero) that the remote peer has is selected as the next piece to be requested from the remote peer.
There is considerable anecdotal evidence that BitTorrent-based P2P technologies can suffer from quality-of-service issues. For commercial applications that offer premium content, such quality-of-service issues would be undesirable.
Thus, there are P2P download problems that have not been resolved by the state of the art technology. What is needed, therefore, are systems and techniques for improving the performance, scaling, and quality of service provided by P2P technologies while reducing the dependence on more expensive content distribution options.